object Example1 {
  def main(args: Array[String]): Unit = {
    println(factorialTailCall(5))
    println(factorial(5))
  }

  // 这个函数是尾递归的吗？
  // 最后一行是：n 乘以 递归调用
  // 所以不是尾递归函数
  def factorial(n: Int): Int = {
    if (n == 1) 1
    else n * factorial(n - 1)
  }

  // 不是尾递归
  def fib(n: Int): Int = {
    if (n == 1 || n == 2) n
    else fib(n - 1) + fib(n - 2)
  }

  // java实现
  // int acc = 1;
  // for (int i = n; i > 0; i--) {
  //     acc = acc * i;
  // }
  // return acc;

  // 尾递归的方式
  // 引入累加器
  // loop(3,1) -> loop(2,3) -> loop(1,6)
  // 使用尾递归的方式模拟循环，纯正的函数式编程中，变量是不可变的：val，所以无法使用循环，只能使用尾递归
  def factorialTailCall(n: Int): Int = {
    // acc 是累加器
    def loop(n: Int, acc: Int): Int = {
      if (n == 1) acc
      else loop(n - 1, n * acc)
    }

    // 返回值是函数调用
    loop(n, 1)
  }
}